package algorithm.sort.practice;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2021/1/1 15:38
 * @Version 1.0
 */
public class test {

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        //从这个数组的非叶子节点开始，从下至上、从左到右进行构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            //构建完了大顶堆或者小顶堆结构后，从数组末尾开始，将数组末尾元素与堆顶元素进行交换，每次都使得数组末尾元素是最大的
            swap(arr, 0, i);
            //交换完成一次就重新调整 大顶堆结构
            adjustHeap(arr, 0, i);
        }
    }

    public static void adjustHeap(int[] arr, int i, int length) {
        //记录下当前堆顶的元素
        int temp = arr[i];
        //从该节点的左子节点开始去找一个值最大的节点，然后和堆顶元素交换
        for (int j = 2 * i + 1; j < length; j++) {
            //判断是否该节点的右子节点比左子节点更大
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                j++;
            }
            //如果子结点有大于temp的，即大于堆顶元素的，就和堆顶元素交换
            if (arr[j] > temp) {
                arr[i] = arr[j];
                //把堆的末尾元素下标 赋值给i，即让堆顶元素放在堆的末尾
                i = j;
            } else {
                //如果没有，说明已经是局部大顶堆 ，直接break
                break;
            }
        }
        //因为是大顶堆，所以将原本小的值放到这个堆的末尾
        arr[i] = temp;
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
